package com.chenken;


/**
 *	 最长公共子序列
 *	https://leetcode-cn.com/problems/longest-common-subsequence/
 *
 *	输入：text1 = "abcde", text2 = "ace" 
 *	输出：3  
 *	解释：最长公共子序列是 "ace" ，它的长度为 3 。
 *
 */
public class LongestSubSequence {

	/**
	 * 	状态:dp(i,j)是text1前i个元素和text2前j个元素的最长公共子序列长度
	 * 	状态转移方程如下：
	 * 	if(a == b){
	 * 		table[row][col] = table[row-1][col-1] + 1;
	 * 	}else{
	 * 		table[row][col] = Math.max(table[row][col-1],table[row-1][col]);
	 * 	}
	 */
	public int longestCommonSubsequence(String text1, String text2) {
		if(text1 == null || text2 == null || "".equals(text1) || "".equals(text2)) {
			return 0;
		}
		char[] textArray1 = text1.toCharArray();
		char[] textArray2 = text2.toCharArray();
		int[][] table = new int[textArray1.length+1][textArray2.length+1];
		for(int row = 1;row < table.length;row++) {
			char char1 = textArray1[row-1];
			for(int col = 1;col < table[row].length;col++) {
				if(char1 == textArray2[col-1]) {
					table[row][col] = table[row-1][col-1] + 1;
				}else {
					table[row][col] = Math.max(table[row][col-1],table[row-1][col]);
				}
			}
		}
		//	取二维数组最后一位
		return table[textArray1.length][textArray2.length];
    }
	
	public static void main(String[] args) {
		//String text1 = "abc", text2 = "def";
		String text1 = "abcde", text2 = "def";
		//String text1 = "abc", text2 = "abc";
		System.out.println(new LongestSubSequence().longestCommonSubsequence(text1, text2));
	}
}
